//输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 
//
// 
//
// 示例 1： 
//
// 输入：head = [1,3,2]
//输出：[2,3,1] 
//
// 
//
// 限制： 
//
// 0 <= 链表长度 <= 10000 
// Related Topics 栈 递归 链表 双指针 👍 350 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {

    /**
     *方法1：递归到链表末尾，利用回溯时获取返回数组
     * 递归传入head.next,终止条件head == null
     * 在递归回溯的时候，将当前结点数值加到返回数组
     * len记录长度，用于初始化结果数组；index记录当前位置索引
     */

    /*int[] res;
    int len = 0,index = 0;

    public int[] reversePrint(ListNode head) {

        recur(head);
        return res;
    }

    void recur(ListNode head){
        if (head == null){
            res = new int[len];
            return;
        }
        len++;
        recur(head.next);
        res[index] = head.val;
        index++;
    }*/

    /**
     * 方法2：创建一个辅助栈，利用栈的先进后出的特点
     */
    public int[] reversePrint(ListNode head) {
        //栈
        LinkedList<Integer> stack = new LinkedList<Integer>();
        //入栈
        while (head != null){
            stack.addLast(head.val);
            head = head.next;
        }

        //返回结果
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = stack.removeLast();
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
